package org.leetcode.easy.leetcode21;

public class Solution
{


    public ListNode mergeTwoLists3(ListNode list1,ListNode list2){
        ListNode dummy  = new ListNode(-1);

        ListNode res = dummy;

        while (list1!=null && list2!=null){
            if (list1.val<=list2.val){
                res.next=list1;
                list1=list1.next;
            }else {
                res.next=list2;
                list2=list2.next;
            }
            res = res.next;
        }

        if (list1==null){
            res.next=list2;
        }else {
            res.next=list1;
        }

        return dummy.next;
    }

    public ListNode mergeTwoLists2(ListNode list1,ListNode list2)
    {
        ListNode preHead = new ListNode(-1);

        ListNode prev = preHead;

        while (list1!=null && list2!=null )
        {
            if (list1.val<=list2.val)
            {
                prev.next=list1;
                list1=list1.next;
            }else {
                prev.next =list2;
                list2=list2.next;
            }

            prev= prev.next;
        }

        prev.next = list1==null?list2:list1;

        return preHead.next;

    }


    public ListNode mergeTwoLists(ListNode list1, ListNode list2)
    {

        if (list1==null)
        {
            return list2;
        }

        if (list2==null)
        {
            return list1;
        }

        ListNode resultList = new ListNode();

        while (list1!=null || list2!=null)
       {
           ListNode listNode = getLast(resultList);

           if (list2==null)
           {
               listNode.next = list1;
               return removeFirst(resultList);
           }

           if (list1==null)
           {
               listNode.next = list2;
               return removeFirst(resultList);
           }

           if (list1.val>= list2.val)
           {
               addNodeLast(list2.val,resultList);
               list2= removeFirst(list2);
           }else {
               addNodeLast(list1.val,resultList);
               list1= removeFirst(list1);
           }
       }
        return removeFirst(resultList);
    }

    public ListNode removeFirst(ListNode listNode)
    {
        if (listNode==null || listNode.next==null)
        {
            return null;
        }
        listNode=listNode.next;

        return listNode;
    }

    public void addNodeLast(int value,ListNode node)
    {
        ListNode listNode = getLast(node);

        listNode.next=new ListNode(value,null);
    }

    public ListNode getLast(ListNode node)
    {
        while (node.next!= null)
        {
            node = node.next;
        }

        return node;
    }

    public void loop(ListNode listNode)
    {
        while (listNode!=null)
        {
            System.out.println(listNode.val);
            listNode=listNode.next;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();

//        ListNode one = new ListNode(1,null);
//        ListNode one = new ListNode(5,null);
        ListNode one = new ListNode(1,new ListNode(2,new ListNode(4,null)));
        ListNode two = new ListNode(1,new ListNode(3,new ListNode(4,null)));
//        ListNode two =new ListNode(2,null);

        ListNode listNode = solution.mergeTwoLists2(one, two);

        solution.loop(listNode);

    }
}
